Informed RRT*: Optimal Sampling-based Path Planning Focused via Direct Sampling of an Admissible Ellipsoidal Heuristic

摘要

Rapidly-exploring random trees (RRTs) are popular in motion planning becausethey find solutions efficiently to single-query problems. Optimal RRTs (RRT*s)extend RRTs to the problem of finding the optimal solution, but in doing soasymptotically find the optimal path from the initial state to every state inthe planning domain. This behaviour is not only inefficient but alsoinconsistent with their single-query nature. For problems seeking to minimize path length, the subset of states that canimprove a solution can be described by a prolate hyperspheroid. We show thatunless this subset is sampled directly, the probability of improving a solutionbecomes arbitrarily small in large worlds or high state dimensions. In thispaper, we present an exact method to focus the search by directly sampling thissubset. The advantages of the presented sampling technique are demonstrated with anew algorithm, Informed RRT*. This method retains the same probabilisticguarantees on completeness and optimality as RRT* while improving theconvergence rate and final solution quality. We present the algorithm as asimple modification to RRT* that could be further extended by more advancedpath-planning algorithms. We show experimentally that it outperforms RRT* inrate of convergence, final solution cost, and ability to find difficultpassages while demonstrating less dependence on the state dimension and rangeof the planning problem.